package backMind

// 0-1背包问题

// 存储背包中物品总重量的最大值

// i表示当前考察哪个物品
// cw 表示当前已经装进去的物品总和，
// items 表示每个物品的质量
// n 表示物品个数
// w 表示背包最大承受重量
// 假设背包可装总重量为100，物品个数为10，物品质量存储在数组items中，则这样调用函数

// ZeroOneBackPack ZeroOneBackPack(0,0,a,10,100)
func ZeroOneBackPack(i, cw int, weights []int, n, w int, maxW *int) {
	// 结束条件判断
	// cw == w 表示背包已经装满了, i == n 表示已经考察完所有的物品
	if cw == w || i == n {
		if cw > *maxW {
			*maxW = cw
		}
		return
	}
	ZeroOneBackPack(i+1, cw, weights, n, w, maxW) // 选择不装第i个物品

	if cw+weights[i] <= w { // 如果要装第i个物品，则需要判断能不能装进去
		cw += weights[i]                              // 累加当前已装重量
		ZeroOneBackPack(i+1, cw, weights, n, w, maxW) // 选择装第i个物品
	}
}
